/* eslint-disable no-console */
import { insertSort } from './insertionSort'

/**
 * 桶排序
 * @param A 需要被排序的数组，输入的数值在区间[0, 1)
 */
export function buckedSort(A: number[]): number[] {
	const n = A.length

	const B = Array<number[]>(n)
	// 建立n个桶
	for (let i = 0; i < n; i += 1) {
		B[i] = []
	}
	// 把源数据按照大小放到对应的桶里
	for (let i = 0; i < n; i += 1) {
		B[Math.floor(n * A[i])].push(A[i])
	}
	// 对每个桶排序
	for (let i = 0; i < n; i += 1) {
		B[i] = insertSort(B[i])
	}

	// 按次序合并桶
	const C: number[] = Array<number>().concat(...B)
	return C
}

console.log(buckedSort([0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1]))
